package class_08;

import java.util.ArrayList;
import java.util.List;
/**
 * 	打印所有的子序列
 * 如果是 abc  
 * 全排列： a   
 * 	    b
 * 		c
 * 		ab
 * 		ac
 * 		bc
 * 		abc
 * 
 * 对于a来说，有两种选择，有a，和没有a
 *对于b来说，也有两种选择，有b,和没有b
 * 两种解决策略：1.每一次都用两个ArrayList 添加，有加的也有不加的，这样的话空间复杂度，会变大.
 *          2.修改char的值，如果先遍历有的情况 ，在遍历没有的情况
 *             [a,b,c]
 *             1. [1,1,1]
 *             2. [1,1,0]
 *			逐渐压入栈中
 *			当i==len的时候，返回该字符串。
 *			
 * @author LOGAN
 *
 */
public class Code_03_Print_All_Subsquences {

	public static void printAllSubsquence(String str) {
		char[] chs = str.toCharArray();
		process(chs, 0);
	}

	public static void process(char[] chs, int i) {
		if (i == chs.length) {
			System.out.println(String.valueOf(chs));
			return;
		}
		process(chs, i + 1);
		char tmp = chs[i];
		chs[i] = 0;
		process(chs, i + 1);
		chs[i] = tmp;
	}
	
	public static void function(String str) {
		char[] chs = str.toCharArray();
		process(chs, 0, new ArrayList<Character>());
	}
	
	public static void process(char[] chs, int i, List<Character> res) {
		if(i == chs.length) {
			printList(res);
			return;
		}
		List<Character> resKeep = copyList(res);
		resKeep.add(chs[i]);
		process(chs, i+1, resKeep);
		List<Character> resNoInclude = copyList(res);
		process(chs, i+1, resNoInclude);
	}
	
	public static void printList(List<Character> res) {
		System.out.println(res.toString());
	}
	
	public static List<Character> copyList(List<Character> list){
		List<Character> characters = new ArrayList<>();
		for(Character c: list){
			characters.add(c);
		}
		return characters;
	}
	

	public static void main(String[] args) {
		String test = "abc";
		function(test);
//		printAllSubsquence(test);
	}

}
